#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <pthread.h>

#define MAX_VET 1000

int vet[MAX_VET];
int n_vet=0;
int n_proc=0;
int vet_amostra[100];
int vet_pivots[100];
int mat_r[20][10][10];
int n_pivots=0;
pthread_barrier_t barr;
//int vet_tam_part[100];


//quicksort sequencial
void qsort_seq(int array[], int begin, int end) {
   if(end - begin > 0) {
    int aux;
    int pivot = array[begin];
    int left = begin + 1;
    int right = end;
    while(left < right) {
        if(array[left] <= pivot) {
            left++;
        } else {
           // Troca o valor de array[left] com array[right]
           aux = array[left];
           array[left] = array[right];
           array[right] = aux;
           // Fim da troca ( equivale a função swap(array[left], array[right]) )
           right--;
        }
    }
    if(array[left] > pivot) {
        left--;
    }
                                          
    // Troca o valor de array[begin] com array[left]
    aux = array[begin];
    array[begin] = array[left];
    array[left] = aux;
    // Fim da troca ( equivale a função swap(array[begin], array[left]) )
    // Faz as chamadas recursivas para as duas partes da lista
    qsort_seq(array, begin, left-1);
    qsort_seq(array, right, end);
   }
}



//fase 1
void phase1 (int i){

    int part=0;
	int i2;
    part = n_vet/n_proc;
	//printf("\n dentro da thread---> %d,%d",part*i,part*(i+1));
    if (i==(n_proc-1))                 // se for a ultima thread, fica com todo o final do vetor
    	qsort_seq(vet,part*i,n_vet-1);
    else	
      	qsort_seq(vet,part*i,part*(i+1)-1);
    int c = (n_proc)*i;
    int c2 = part*i;
    for (i2=0;i2<n_proc;i2++){       //preenche o vetor de amostras regulares
    	vet_amostra[c+i2] = vet[i*(n_vet/n_proc)+i2*n_vet/(n_proc*n_proc)] ; 
    }
 
}

//inicio do psrs
void *psrs(void *threadid){

	phase1((int)threadid);  
	pthread_exit(NULL);
}

//fase 2
void *phase2 (void *threadid){
	coloca_mat(threadid);
	//printf("thread --->>%d",threadid);
	//barrier aqui
	pthread_barrier_wait(&barr);
	troca(threadid);
	pthread_exit(NULL);

}

//preenche a matriz 
void coloca_mat(void *threadid){
	int i=0;
	int i2=0;
	int i3=0;
    int i4=0;
	int j=(int)threadid;
	int k=0;
    int x=0;
	int part = n_vet/n_proc;
	int c=part*(int)threadid;
	
	while (i2<n_pivots){ // percorre 
		while (vet[c+i]<=vet_pivots[i2]){  //preenche a matriz com as porçoes limitadas pelos pivos em cada processo
			mat_r[i3][j][k]=vet[c+i];      
			i3++;
			i++;
		}
		k++;
		i2++;
        
		i3=0;
        x++;
	}
	if((int)threadid==(n_proc-1)){    //faz o mesmo mas qdo nao ha limitante superior que seja pivo, neste caso final do vetor
		while(c+i<n_vet){
            mat_r[i3][j][k]=vet[c+i];
            i++;
            i3++;
		}
	}
	else{ //neste caso sem ser final do vetor
		while((c+i)<(part*((int)threadid+1))){
            mat_r[i3][j][k]=vet[c+i];
            i++;
            i3++;
		}
	}
}


//realiza a troca entre as porçoes e o vetor original(fase 3)
int troca (void  *threadid){

    int c=(n_vet/n_proc)*(int)threadid;
    int j=0;
    int i=0;
    int i2=0;
    
    int k = (int)threadid;
    
    for (j=0;j<n_proc;j++){
        while(mat_r[i][j][k]!=0){
            vet[c+i2]=mat_r[i][j][k];
            i++;
            i2++;
            
                                    
        }
        i=0;
    }
    //realiza o quicksort no partes de cada vetor, no final(fase 4)
    if ((int)threadid==0)
        qsort_seq(vet,(n_vet/n_proc)*(int)threadid,(n_vet/n_proc)*((int)threadid+1));
    else
        qsort_seq(vet,(n_vet/n_proc)*(int)threadid,(n_vet/n_proc)*((int)threadid+1));
    
    
    
}



int main (int argc, char *argv[]){

	int n_amostras;
	int rc;
	int n = atoi(argv[1]);
	int nthreads = atoi(argv[2]);
    int i;
	pthread_t threads[nthreads];
    n_vet = n;
    n_proc = nthreads;	
	srand (time(NULL));
	

    
    //inicializa o barrier
    pthread_barrier_init(&barr, NULL, nthreads);

    //gera os numeros aleatoriamente
	for(i=0;i<n;i++){
	    vet[i] = rand()*(1e2/RAND_MAX);
        //printf("%d\n",vet[i]);
	}
   	//cria os processos da fase 1
	for(i=0;i<(nthreads);i++){
		rc = pthread_create(&threads[i],NULL,psrs,(void *)i);
	}
    for(i=0;i<nthreads;i++)
        pthread_join(threads[i],NULL);	
    /*
    printf("\n---------vetor de amostras---------------------\n");
    i=0;
    while (vet_amostra[i]!=0){
    	printf("\n%d",vet_amostra[i]);
    	i++;
    }
    */

    //organiza o vetor de amostra
    qsort_seq(vet_amostra,0,i-1);
    i=0;
    
    //preenche o vetor de pivots
    for (i=0;i<n_proc;i++){
    	if(i==n_proc-1)
            vet_pivots[i] = vet_amostra[i*n_proc+(n_proc/2)];
        else
            vet_pivots[i] = vet_amostra[(i+1)*n_proc+(n_proc/2)-1] ; 

    }
    /*
    printf("\n---------vetor de pivots---------------------\n");
    for(i=0;i<n_proc-1;i++){
        printf("\n%d",vet_pivots[i]);
        n_pivots++;
    }
    */
    //cria os processos da fase 2 em diante
    for(i=0;i<(nthreads);i++){
		rc = pthread_create(&threads[i],NULL,phase2,(void *)i);
	}
    for(i=0;i<nthreads;i++)
        pthread_join(threads[i],NULL);
    /*printf("\n----------- vetor ordenado -------------------\n");
    for(i=0;i<n;i++){
        printf("\n%d",vet[i]);
    }
    */
    //printf("\n");
	//pthread_exit(NULL);
	
    //saida especificada
    for(i=0;i<n_vet;i++){
        if(i==n_vet-1)
            printf("%d.",vet[i]);
        else
            printf("%d, ",vet[i]);
    }	

	return 1;

}
